import java.util.ArrayList;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Graph {
    private static ArrayList<Message> vertexList;//存储顶点集合
    private int[][] edges;//存储图对应的邻接矩阵
    int[] d = new int[15];//辅助向量
    int min = 0;//记录每次选取的最短路径的终点
    boolean[] s = {true, true, true, true, true, true, true, true, true, true, true, true, true, true, true};//每次选取点数保存到这，避免重复
    public static Message[] firstList;//存放各个景点的最短路径

    //插入结点
    public void insertVertex(Message vertex) {
        vertexList.add(vertex);
    }

    public Graph(int n) {
//        初始化矩阵和vertexList
        edges = new int[n][n];
        for (int i = 0; i < edges.length; i++) {
            for (int j = 0; j < edges[i].length; j++) {
                if (i == j) {
                    edges[i][j] = 0;
                } else {
                    edges[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        vertexList = new ArrayList<Message>(n);
//        sideList = new ArrayList<>(20);
        firstList = new Message[n];
    }

    //    显示图对应的矩阵
    public void showGraph() {
        for (int i = 0; i < edges.length; i++) {
            for (int j = 0; j < edges[i].length; j++) {

                if (edges[i][j] == Integer.MAX_VALUE) {
                    System.out.print("\t" + "∞" + "\t");
                } else {
                    if (i == 6 && j == 7 || i == 7 && j == 6) {
                        System.out.print("\t" + edges[i][j]);
                    } else {
                        System.out.print("\t" + edges[i][j] + "\t");
                    }
                }
                if (j < edges[i].length - 1) {

                    System.out.print(" ");
                }
            }
            System.out.println();
        }
    }

    //添加边
    public void insertCharEdge(String a, String b, int weight) {
        int v1 = 0;
        int v2 = 0;
        for (int i = 0; i < vertexList.size(); i++) {
            if (vertexList.get(i).getName().equals(a)) {
                v1 = i;
            } else if (vertexList.get(i).getName().equals(b)) {
                v2 = i;
            } else if (v2 != 0 && v1 != 0) {
                break;
            }
        }
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
    }

    /**
     * 迪杰斯特拉算法
     * @param start
     * @return
     */
    public int[] shortPath(int start) {
        for (int i = 0; i < d.length; i++) {
            d[i] = edges[start][i];
        }
        s[start] = false;
        int count = 0;//最短路径的下标
        for (int k = 0; k < d.length; k++) {
            min = 0;
            for (int i = 0; i < d.length; i++) {//选取最短路径保存到min
                if (d[i] > 0 && d[i] != Integer.MAX_VALUE && s[i]) {
                    if (min == 0) {
                        min = d[i];
                        count = i;
                        continue;
                    } else {
                        if (min > d[i]) {
                            min = d[i];
                            count = i;
                        }
                    }
                }


            }//选取最短路径保存到min
            s[count] = false;
            if (firstList[count] == null) {
                insertPoint(count);
            }
            for (int j = 0; j < vertexList.size(); j++) {//j是景点
                if (s[j] && edges[count][j] != 0 && d[j] == Integer.MAX_VALUE) {
                    if (edges[j][start] < edges[count][j] + min) {
                        //如果到开始的权值小于最小权值+(min,j)
                        d[j] = edges[j][start];
                        insertPoint(j);
                    } else if (edges[j][start] == Integer.MAX_VALUE && edges[count][j] == Integer.MAX_VALUE) {
                        continue;
                    } else {
                        d[j] = edges[count][j] + min;
                        if (firstList[j] == null) {
                            firstList[j] = new Message();
                            firstList[j].setNextMessage(firstList[count].getNextMessage());//把当前景点存放进去
                        } else {
                            firstList[j].setNextMessage(firstList[count].getNextMessage());
                        }
                        insertPoint(j);
                    }
                }
            }


        }
        return d;
    }

    /**
     * 插入节点
     *
     * @param j 传入在vertexList的下标
     */
    public void insertPoint(int j) {
        Message message = vertexList.get(j);//创建景点对象
        if (firstList[j] == null) {
            firstList[j] = new Message();
            firstList[j].setNextMessage(message);//把当前景点存放进去
        } else {
            Message nextMessage = firstList[j].getNextMessage();//取出存放头节点的对象
            if (nextMessage == null) {//为空说明没有存放任何景点
                firstList[j].setNextMessage(message);//就把当前景点存放进去
            } else {//不为空说明已有景点，把当前景点放到头节点，以前节点放到当前节点的下一个节点（头插法）
                message.setNextMessage(nextMessage);
                firstList[j].setNextMessage(message);
            }
        }

    }

    /**
     * 输出从start开始全部的路径
     *
     * @param start
     */
    public void sysList(int start) {
        int[] ints = shortPath(start);
        for (int i = 0; i < firstList.length; i++) {
            if (i != start) {
                System.out.print(vertexList.get(start).getName() + "->");
                searchPoint(firstList[i].getNextMessage());
                System.out.println("\t总距离为：" + ints[i] + "米");
                System.out.println();
            }
        }
        cleanVariable();
    }

    /**
     * 输出从start到end的路径
     *
     * @param start
     */
    public void sysList(int start, int end) {
        int[] ints = shortPath(start);
        System.out.print(vertexList.get(start).getName() + "->");
        searchPoint(firstList[end].getNextMessage());
        System.out.println("\t总距离为：" + ints[end] + "米");
        System.out.println();
        cleanVariable();
    }

    /**
     * 清除变量中的数据
     */
    public void cleanVariable() {
        d = new int[15];//辅助向量
        min = 0;//记录每次选取的最短路径的终点
        for (int i = 0; i < s.length; i++) {
            s[i] = true;
            firstList[i] = null;
        }
    }

    /**
     * 使用递归输出链表
     *
     * @param message
     */
    public void searchPoint(Message message) {
        if (message.getNextMessage() != null) {
            searchPoint(message.getNextMessage());
            System.out.print("->" + message.getName());
        } else {
            System.out.print(message.getName());
        }
    }

    /**
     * 展示全部景点信息
     */
    public static void showPoint() {
        System.out.println("------------------------------------------------");
        System.out.println("编号 |景区名称|简介");
        for (int i = 0; i < vertexList.size(); i++) {
            System.out.println(vertexList.get(i).getCode() + "\t|" + vertexList.get(i).getName() +
                    "\t\t|" + vertexList.get(i).getSynopsis());
        }
    }
    public int guibi(String count){
        if(count.length() <=2){
            Pattern pattern = Pattern.compile("[0-9]*");
            Matcher isNum = pattern.matcher(count);
            if( !isNum.matches() ){
                System.out.println("输入错误，请重新输入");
                return -1;
            }else{
                return Integer.parseInt(count);
            }
        }else{
            System.out.println("输入错误，请重新输入");
            return -1;
        }
    }
    /**
     * 第二个界面
     */
    public void showAllPoint() {
        boolean flags = true;
        Scanner scanner = new Scanner(System.in);
        int start = 0;
        int end = 0;
        String count;
        while (flags) {
            System.out.println("------------------------------------------------");
            System.out.println("\t\t\t\t\t1.查看从当前景点到全部景点的路径");
            System.out.println("\t\t\t\t\t2.查看从当前景点到指定景点的路径");
            System.out.println("\t\t\t\t\t3.返回上一层");
            System.out.print("请输入：");
            String s = scanner.next();
            switch (s) {
                case "1":
                    System.out.print("请输入当前景点编号：");
                    count = scanner.next();
                    start = guibi(count);
                    if(start!=-1){
                        if(start<15&&start>=0){

                            sysList(start);
                        }else{
                            System.out.println("请输入0-14之内的编号");
                        }
                    }
                    break;
                case "2":
                    System.out.print("请输入当前景点编号：");
                    count = scanner.next();
                    start = guibi(count);
                    System.out.print("请输入目的景点编号：");
                    count = scanner.next();
                    end = guibi(count);
                    if(start!=-1&&end!=-1){
                        if(start<15&&start>=0&&end<15&&end>=0){

                            sysList(start, end);
                        }else{
                            System.out.println("请输入0-14之内的编号");

                        }                    }
                    break;
                case "3":
                    flags = false;
                    break;
                default:
                    System.out.println("输入错误，请重新输入");
                    break;
            }
        }
    }
}

